package top.ivansong92.example.leetcode.learning.data.struct.array;


import org.junit.Test;
import top.ivansong92.example.leetcode.learning.data.struct.array.sort.ArraySort;
import top.ivansong92.example.leetcode.learning.data.struct.array.sort.BubbleSort;

import java.util.*;
import java.util.stream.Collectors;

public class TestExample {

    @Test
    public void test1() {
        System.out.println(removeRepeatNumber(new int[]{3, 3, 3, 3, 3, 3, 3}));
    }

    @Test
    public void test2() {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
    }


    @Test
    public void test4() {
        System.out.println(plusOne(new int[]{1, 2, 3}));

        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < 5000; i++) {
            list.add(i);
        }
        System.out.println(list);

        Map<TestHash, Integer> map = new HashMap<>();

        for (int i = 0; i < 128; i++) {
            map.put(new TestHash("" + i), i);
        }


    }


    @Test
    public void test3() {

        Random random = new Random();
        int len_1 = random.nextInt(10000000);
        Integer[] num1 = new Integer[len_1];
        for (int i = 0; i < len_1; i++) {
            num1[i] = random.nextInt(10000000);
        }
        int len_2 = random.nextInt(10000000);
        Integer[] num2 = new Integer[len_2];
        for (int i = 0; i < len_2; i++) {
            num2[i] = random.nextInt(10000000);
        }
        System.out.println(Arrays.stream(num1).collect(Collectors.toList()));
        System.out.println(Arrays.stream(num2).collect(Collectors.toList()));
    }

    /**
     * 26. 删除排序数组中的重复项
     */
    private int removeRepeatNumber(int[] array) {
        if (array == null || array.length <= 0) {
            return 0;
        }

        int res = 0;
        for (int i = 0; i < array.length; ) {
            if (res == i || array[res] == array[i]) {
                i++;
                continue;
            }
            res++;
            array[res] = array[i];
        }
        return res + 1;
    }


    //22
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i - 1] > prices[i]) {
                continue;
            }
            res += prices[i] - prices[i - 1];
        }
        return res;
    }


    /**
     * 189. 旋转数组
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1 || k % nums.length <= 0) {
            return;
        }

        int step = k % nums.length;
        for (int i = 0; i < step; i++) {
            int temp = nums[nums.length - 1];
            for (int j = nums.length - 2; j >= 0; j--) {
                nums[j + 1] = nums[j];
            }
            nums[0] = temp;
        }
    }


    public boolean containsDuplicate(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return false;
        }

        Set<Integer> set = new HashSet<>();

        for (int nu : nums) {
            if (set.contains(nu)) {
                return true;
            }
            set.add(nu);
        }
        return false;
    }

    /**
     * 136. 只出现一次的数字
     *
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i += 2) {
            if (i + 1 == nums.length) {
                return nums[i];
            }
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }

        }
        return 0;
    }


    /**
     * 136. 只出现一次的数字
     *
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        if (nums.length < 2) {
            return nums[0];
        }
        int res = 0;

        for (int nu : nums) {
            res ^= nu;
        }
        return res;
    }


    /**
     * 350. 两个数组的交集 II
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }

        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int count = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int i = 0;
        int j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                res[count++] = (nums1[i]);
                i++;
                j++;
            }
        }

        return Arrays.copyOfRange(res, 0, count);
    }


    /**
     * 66. 加一
     *
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return null;
        }
        int plus = 1;
        int[] newDigits = new int[digits.length];

        for (int i = digits.length - 1; i >= 0; i--) {
            int val = digits[i] + plus;
            if (val >= 10) {
                plus = 1;
                newDigits[i] = val - 10;
            } else {
                plus = 0;
                newDigits[i] = val;
            }
        }

        if (plus > 0 && digits.length < Integer.MAX_VALUE) {
            int[] res = new int[digits.length + 1];
            res[0] = plus;
            for (int i = 0; i < newDigits.length; i++) {
                res[i + 1] = newDigits[i];
            }
            return res;
        }

        return newDigits;
    }


    /**
     * 283. 移动零
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int not0Index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                continue;
            }
            if (not0Index == i) {
                not0Index++;
                continue;
            }
            nums[not0Index++] = nums[i];
            nums[i] = 0;
        }
    }

    public void moveZeroes2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int len = nums.length;
        int not0Index = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != 0) {
                nums[not0Index++] = nums[i];
            }
        }
        for (int i = not0Index; i < len; i++) {
            nums[i] = 0;
        }
    }

    public void moveZeroes3(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int len = nums.length;
        int i = 0, k = 0;
        while (i < len) {
            if (nums[i] != 0) {
                if (i == k) {
                    k++;
                } else {
                    nums[k++] = nums[i];
                    nums[i] = 0;
                }
            }
            i++;
        }

    }


    /**
     * 1. 两数之和
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }

        Map<Integer, List<Integer>> numsIndexMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            List<Integer> indexList = numsIndexMap.get(nums[i]);
            if (indexList == null) {
                indexList = new ArrayList<>();
            }
            indexList.add(i);
            numsIndexMap.put(nums[i], indexList);
        }
        int[] res = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int surplus = target - nums[i];
            List<Integer> indexList = numsIndexMap.get(surplus);
            if (indexList == null) {
                continue;
            }
            if (indexList.size() > 1) {
                res[0] = indexList.get(0);
                res[1] = indexList.get(1);
                return res;
            }

            if (indexList.size() == 1 && indexList.get(0) == i) {
                continue;
            }
            res[0] = i;
            res[1] = indexList.get(0);
            return res;
        }
        return new int[0];
    }

    public int[] twoSum2(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return new int[0];
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i ++) {
            int ele = nums[i];
            int plus = target - ele;
            Integer plusIndex = map.get(plus);
            if (plusIndex != null) {
                return new int[]{plusIndex, i};
            }
            map.put(ele, i);
        }
        return new int[0];
    }


    /**
     * 15. 三数之和
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return Collections.emptyList();
        }

        int len = nums.length;
        if (len == 3) {
            return nums[0] + nums[1] + nums[2] == 0 ? Collections.singletonList(Arrays.asList(nums[0], nums[1], nums[2])) : Collections.emptyList();
        }

        Set<String> filter = new HashSet<>();

        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);

        for (int i = 0; i <= len - 3; i++) {
            int val = nums[i];
            if (val > 0) {
                break;
            }

            if (i > 0 && val == nums[i - 1]) {
                continue;
            }
            int start = i + 1, end = len - 1;
            while (start < end) {
                int startVal = nums[start];
                int endVal = nums[end];
                int tmp = val + startVal + endVal;
                if (tmp == 0) {
                    String key = val + "," + startVal + "," + endVal;
                    if (!filter.contains(key)) {
                        res.add(Arrays.asList(val, startVal, endVal));
                        filter.add(key);
                    }
                    start ++;
                    end --;
                } else if (tmp > 0){
                    end --;
                } else {
                    start ++;
                }
            }
        }
        return res;
    }

    public List<List<Integer>> threeSumV2(int[] nums) {
        if (nums == null || nums.length < 3) {
            return Collections.emptyList();
        }

        int len = nums.length;
        if (len == 3) {
            return nums[0] + nums[1] + nums[2] == 0 ? Collections.singletonList(Arrays.asList(nums[0], nums[1], nums[2])) : Collections.emptyList();
        }


        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);

        for (int i = 0; i <= len - 3; i++) {
            int val = nums[i];
            if (val > 0) {
                break;
            } else if (i > 0 && val == nums[i - 1]) {
                continue;
            }

            int start = i + 1, end = len - 1;
            while (start < end) {
                int startVal = nums[start];
                int endVal = nums[end];
                int tmp = val + startVal + endVal;
                if (tmp == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(val);
                    list.add(startVal);
                    list.add(endVal);
                    res.add(list);
                    start ++;
                    end --;
                    while (start < end && nums[start] == nums[start - 1]) {
                        start++;
                    }
                    while (start < end && nums[end] == nums[end + 1]) {
                        end --;
                    }
                } else if (tmp > 0){
                    end --;
                } else {
                    start ++;
                }
            }
        }
        return res;
    }


    /**
     * 18. 四数之和
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) {
            return Collections.emptyList();
        }

        int len = nums.length;
        if (len == 4) {
            return nums[0] + nums[1] + nums[2] + nums[3] == target ? Collections.singletonList(Arrays.asList(nums[0], nums[1], nums[2], nums[3])) : Collections.emptyList();
        }

        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);

        for(int i = 0; i <= len - 4; i ++) {
            int s1 = nums[i];
            if (i > 0 && s1 == nums[i - 1]) {
                continue;
            }
            for (int j = len - 1; j >= i + 3; j--) {
                int s2 = nums[j];
                if (j < len - 1 && s2 == nums[j + 1]) {
                    continue;
                }

                int plus = target - s1 - s2;
                int start = i + 1, end = j -1;
                while (start < end) {
                    int startVal = nums[start],
                            endVal = nums[end],
                            val = startVal + endVal;
                    if (val == plus) {
                        res.add(Arrays.asList(s1, startVal, endVal, s2));
                        start ++;
                        end --;
                        while (start < end && nums[start] == nums[start - 1]) {
                            start ++;
                        }

                        while (start < end && nums[end] == nums[end + 1]) {
                            end --;
                        }
                    } else if (val > plus) {
                        end --;
                    } else {
                        start ++;
                    }

                }
            }
        }

        return res;
    }

    /**
     * 454. 四数相加 II
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        if (nums1.length == 1 && nums2.length == 1 && nums3.length == 1 && nums4.length == 1) {
            return nums1[0] + nums2[0] + nums3[0] + nums4[0] == 0 ? 1 : 0;
        }

        Map<Integer, Integer> mergeMap = new HashMap<>();
        for (int n1 : nums1) {
            for (int n2 : nums2) {
                int val = n1 + n2;
                Integer count = mergeMap.get(val);
                if (count == null) {
                    count = 0;
                }
                count++;
                mergeMap.put(val, count);
            }
        }

        int res = 0;
        for (int n3 : nums3) {
            for (int n4 : nums4) {
                int val = -(n3 + n4);
                Integer count = mergeMap.get(val);
                if (count == null) {
                    continue;
                }
                res += count;
            }
        }
        return res;
    }


    @Test
    public void testthreeSumClosest() {
        System.out.println(threeSumClosest(new int[]{1,1,1,1}, 0));;
    }

    /**
     * 16. 最接近的三数之和
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            return Integer.MIN_VALUE;
        }

        int len = nums.length;
        if (len == 3) {
            return nums[0] + nums[1] + nums[2];
        }

        Arrays.sort(nums);

        Integer res = null;
        int step = Integer.MAX_VALUE;

        for (int i = 0; i <= len - 3; i++) {
            int val = nums[i];
            if (i > 0 && val == nums[i - 1]) {
                continue;
            }

            int start = i + 1, end = len - 1;
            while (start < end) {
                int startVal = nums[start];
                int endVal = nums[end];
                int tmp = val + startVal + endVal - target;
                if (tmp == 0) {
                    return target;
                } else if (tmp > 0){
                    if (step > tmp) {
                        step = tmp;
                        res = tmp + target;
                    }
                    end --;
                } else {
                    tmp = -tmp;
                    if (step > tmp) {
                        step = tmp;
                        res = -tmp + target;
                    }
                    start ++;
                }
            }
        }
        return res;
    }

    private static class TestHash {
        private String val;

        public TestHash(String val) {
            this.val = val;
        }

        @Override
        public int hashCode() {
            return 1;
        }
    }

    @Test
    public void test5() {

        System.out.println(lengthOfLongestSubstring("dvdf"));
    }

    @Test
    public void test6() {
        int[] nums = new int[]{2, 2, 1, 2, 1, 0, 1};
        ArraySort arraySort = new BubbleSort();
        arraySort.sort(nums);
        // sortColorsV2(nums);
        System.out.println(Arrays.stream(nums).boxed().collect(Collectors.toList()));
    }

    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int max = 0;
        int start = 0, end = 0;
        Set<Character> sets = new HashSet<>();
        sets.add(s.charAt(start));
        while (start < s.length() && end < s.length()) {
            if (end <= start) {
                end++;
                continue;
            }

            char ch = s.charAt(end);
            if (sets.contains(ch)) {
                max = Math.max(max, end - start);
                int temp = start;
                start = s.indexOf(ch, start) + 1;
                char[] chars = s.substring(temp, start).toCharArray();
                for (char cr : chars) {
                    sets.remove(cr);
                }
                sets.add(s.charAt(start));
            } else {
                sets.add(ch);
                end++;
            }
        }
        max = Math.max(max, end - start);

        return max;
    }


    /**
     * 541. 反转字符串 II
     * @param s
     * @param k
     * @return
     */
    public String reverseStr(String s, int k) {
        if (s == null || s.length() < 2 || k == 1) {
            return s;
        }

        List<String> subList = new ArrayList<>();
        int len = s.length();
        for (int i = 0; i < len; i += k) {
            subList.add(s.substring(i, Math.min(i + 2, len)));
        }
        StringBuilder res = new StringBuilder();
        for(int i = 0; i < subList.size(); i ++) {
            String sub = subList.get(i);
            if (i % 2 == 0) {
                int a = 0, b = sub.length() - 1;
                char[] chars = new char[sub.length()];
                while (a < b) {
                    chars[b] = sub.charAt(a);
                    chars[a] = sub.charAt(b);
                    a ++;
                    b --;
                }
                if (a == b) {
                    chars[a] = sub.charAt(a);
                }
                res.append(new String(chars));
            } else {
                res.append(sub);
            }
        }
        return res.toString();
    }

    /**
     * 49. 字母异位词分组
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return Collections.emptyList();
        }

        String[] temps = new String[strs.length];
        Set<String> strings = new HashSet<>();
        for (int i = 0; i < temps.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            temps[i] = new String(chars);
            strings.add(temps[i]);
        }
        List<List<String>> result = new ArrayList<>();
        for (String s : strings) {
            List<String> list = new ArrayList<>();
            for (int i = 0; i < temps.length; i++) {
                if (temps[i].equals(s)) {
                    list.add(strs[i]);
                }
            }
            result.add(list);
        }
        return result;
    }


    public List<List<String>> groupAnagramsV2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return Collections.emptyList();
        }

        Map<String, List<String>> groupMap = new HashMap<>();
        char[] chars;
        for (String s : strs) {
            chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = groupMap.computeIfAbsent(key, k -> new ArrayList<>());
            list.add(s);
        }
        return new ArrayList<>(groupMap.values());
    }


    public List<List<String>> groupAnagrams1(String[] strs) {
        if (strs == null || strs.length == 0) {
            return Collections.emptyList();
        }

        Map<String, List<String>> resultMap = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> val = resultMap.get(key);
            if (val == null) {
                val = new ArrayList<>();
            }
            val.add(strs[i]);
            resultMap.put(key, val);
        }
        return new ArrayList<>(resultMap.values());
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        boolean res = false;
        for (int i = 0; i < matrix.length; i++) {
            if (target > matrix[i][matrix[i].length - 1]) {
                continue;
            }

            if (target < matrix[i][0]) {
                break;
            }

            int k = 0, j = matrix[i].length - 1;
            if (target == matrix[i][j] || target == matrix[i][k]) {
                res = true;
                break;
            }
            while (k < j) {
                int av = (k + j) / 2;
                int val = matrix[i][av];
                if (val == target) {
                    res = true;
                    break;
                }

                if (j == av || k == av) {
                    break;
                }
                if (val < target) {
                    k = av;
                } else {
                    j = av;
                }
            }
            if (res) {
                break;
            }
        }
        return res;
    }

    /**
     * 75. 颜色分类
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int[] counter = new int[3];
        for (int n : nums) {
            if (n >= counter.length) {
                return;
            }
            counter[n] = counter[n] + 1;
        }
        int index = 0;
        for (int i = 0; i < 3; i++) {
            int c = counter[i];
            for (int j = 0; j < c; j++) {
                nums[index] = i;
                index++;
            }
        }
    }

    public void sortColorsV2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        int zeroEnd = -1, twoStart = nums.length;
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int startVal = nums[start];
            switch (startVal) {
                case 0:
                    if (start == 0) {
                        zeroEnd = 0;
                    } else {
                        zeroEnd++;
                        swap(nums, start, zeroEnd);
                    }
                    start++;
                    break;
                case 1:
                    start++;
                    break;
                case 2:
                    if (end == nums.length - 1) {
                        twoStart = nums.length - 1;
                    } else {
                        twoStart--;
                    }
                    swap(nums, start, twoStart);
                    end--;
                    break;
                default:
                    return;
            }
        }

    }

    private void swap(int[] nums, int index1, int index2) {
        int index1Val = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = index1Val;
    }

    /**
     * 215. 数组中的第K个最大元素
     */
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length < k) {
            return -1;
        }

        return doFind(nums, 0, nums.length - 1, k);
    }

    public int doFind(int[] nums, int start, int end, int k) {
        if (start > end) {
            return -1;
        }
        if (start == end) {
            if (start == k - 1) {
                return nums[start];
            }
            return -1;
        }

        int i_start = start, i_end = end;
        int val = nums[start];

        while (i_start < i_end) {
            while (i_start < i_end && nums[i_end] <= val) {
                i_end--;
            }
            nums[i_start] = nums[i_end];
            while (i_start < i_end && nums[i_start] >= val) {
                i_start++;
            }
            nums[i_end] = nums[i_start];
        }
        nums[i_start] = val;
        int plus = i_start - k + 1;

        if (plus == 0) {
            return nums[i_start];
        } else if (plus > 0) {
            return doFind(nums, start, i_start - 1, k);
        } else {
            return doFind(nums, i_start + 1, end, k);
        }
    }

    /**
     * 209. 长度最小的子数组
     */
    public int minSubArrayLen(int target, int[] nums) {
        return 0;
    }


    @Test
    public void test7() {
        int[] nums = new int[20];
        Random rand = new Random();
        for (int i = 0; i < nums.length; i++) {
            nums[i] = (rand.nextInt(100) + 1);
        }
        System.out.println("org:" + Arrays.toString(nums));
        System.out.println("topN:" +Arrays.toString(getTopN(nums, 5)));
        System.out.println("bottomN:" + Arrays.toString(getBottomN(nums, 5)));
        Arrays.sort(nums);
        System.out.println("sort:" + Arrays.toString(nums));
    }

    public int[] getTopN(int[] array, int n) {
        Integer[] res = new Integer[n];

        for(int i = 0; i < array.length; i ++) {
            if (i < n) {
                res[i] = array[i];
                continue;
            }

            if (i == n) {
                reBalance(res);
            }

            int val = array[i];
            if (val <= res[0]) {
                continue;
            }

            res[0] = val;
            reBalance(res);
        }

        return Arrays.stream(res).mapToInt(Integer::intValue).toArray();
    }


    private void reBalance(Integer[] array) {
        int len = array.length;
        for (int i = len / 2; i >= 0; i--) {
            Integer val = array[i];
            if (val == null) {
                break;
            }
            if ((2 * i + 1) < len && array[2 * i + 1] < val) {
                swap(array, i, 2 * i + 1);
                val = array[i];
            }

            if ((2 * i + 2) < len && array[2 * i + 2] < val) {
                swap(array, i, 2 * i + 2);
            }
        }
    }


    public int[] getBottomN(int[] array, int n) {
        Integer[] res = new Integer[n];

        for(int i = 0; i < array.length; i ++) {
            if (i < n) {
                res[i] = array[i];
                continue;
            }

            if (i == n) {
                reBalanceV2(res);
            }

            int val = array[i];
            if (val >= res[0]) {
                continue;
            }

            res[0] = val;
            reBalanceV2(res);
        }

        return Arrays.stream(res).mapToInt(Integer::intValue).toArray();
    }

    private void reBalanceV2(Integer[] array) {
        int len = array.length;
        for (int i = len / 2; i >= 0; i--) {
            Integer val = array[i];
            if (val == null) {
                break;
            }
            if ((2 * i + 1) < len && array[2 * i + 1] > val) {
                swap(array, i, 2 * i + 1);
                val = array[i];
            }

            if ((2 * i + 2) < len && array[2 * i + 2] > val) {
                swap(array, i, 2 * i + 2);
            }
        }
    }

    private void swap(Integer[] array, int index1, int index2) {
        Integer tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }

    @Test
    public void testV2() {
        System.out.println(removeElement(new int[]{3,2,2,3}, 3));
    }

    /**
     * 27. 移除元素
     * @param nums
     * @param val
     * @return
     */

    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int len = nums.length;
        int k = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }



    @Test
    public void testV3() {
        System.out.println(removeDuplicates(new int[]{0,0,1,1,1,2,2,3,3,4}));
    }

    /**
     * 26. 删除有序数组中的重复项
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        int len = nums.length;
        if (len == 1) {
            return len;
        }
        int k = 0;
        for(int i = 1; i < len; i ++) {
            if (nums[i] != nums[k]) {
                k ++;
                nums[k] = nums[i];
            }
        }
        return k + 1;
    }

    /**
     * 345. 反转字符串中的元音字母
     * @param s
     * @return
     */
    private static Set<Character> VOWELS = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
    public String reverseVowels(String s) {
        if (s == null || s.length() < 2) {
            return s;
        }
        int i = 0, j = s.length() - 1;
        char[] chars = new char[s.length()];
        while (i < j) {
            char ch1 = s.charAt(i);
            char ch2 = s.charAt(j);
            if (VOWELS.contains(ch1) && VOWELS.contains(ch2)) {
                chars[i] = ch2;
                chars[j] = ch1;
                i ++;
                j --;

            } else if (VOWELS.contains(ch1)) {
                chars[j] = ch2;
                j --;
            } else if (VOWELS.contains(ch2)) {
                chars[i] = ch1;
                i ++;
            } else {
                chars[i] = ch1;
                chars[j] = ch2;
                i ++;
                j --;
            }
        }
        if (i == j) {
            chars[i] = s.charAt(i);
        }
        return new String(chars);
    }



}
